\section{Transformation algorithms}

In this section, we will discuss algorithms that transform ranges by changing the values of elements and removing and re-ordering elements.

\subsection{\texorpdfstring{\cpp{std::transform}}{\texttt{std::transform}}}
\index{\cpp{std::transform}}

The most straightforward transformation possible is to apply a transformation function to each element. The \cpp{std::transform} algorithm provides this functionality in unary and binary variants (input from one or two ranges).

\cppversions{\texttt{transform}}{\CC98}{\CC20}{\CC17}{\CC20}

\constraints{\texttt{input\_range -> output\_iterator}\newline\texttt{(input\_range, input\_iterator) -> output\_iterator}}{\texttt{forward\_range -> forward\_iterator}\newline\texttt{(forward\_range, forward\_iterator) -> forward\_iterator}}{N/A}{\texttt{unary\_functor}\newline\texttt{binary\_functor}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/6W38nMh6b}{\ExternalLink}}
\footnotesize Example of unary and binary version of \cpp{std::transform}. Note that the output iterator can be one of the input ranges' begin iterator (line 4 and 12).
\tcblower
\cppfile{code_examples/algorithms/transform_code.h}
\end{codebox}

Note that \cpp{std::transform} does not guarantee strict left-to-right evaluation. If that is required, use \cpp{std::for_each} instead.

\subsection{\texorpdfstring{\cpp{std::remove}, \cpp{std::remove_if}}{\texttt{std::remove}, \texttt{std::remove\_if}}}
\index{\cpp{std::remove}}
\index{\cpp{std::remove_if}}

The \cpp{std::remove} and \cpp{std::remove_if} algorithms "remove" elements that match the given value or for which the given predicate evaluates to true.

Because the algorithms cannot resize the underlying range, the removal is achieved by moving the other elements in the range. The algorithms then return an iterator beyond the last not removed element, i.e. the new end iterator.

\cppversions{\texttt{remove, remove\_if}}{\CC98}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{forward\_range}}{\texttt{forward\_range}}{N/A}{\texttt{unary\_predicate}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/eb56eshTq}{\ExternalLink}}
\footnotesize Example of using \cpp{std::remove} and \cpp{std::remove_if}.
\tcblower
\cppfile{code_examples/algorithms/remove_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::replace}, \cpp{std::replace_if}}{\texttt{std::replace}, \texttt{std::replace\_if}}}
\index{\cpp{std::replace}}
\index{\cpp{std::replace_if}}

The \cpp{std::replace} and \cpp{std::replace_if} algorithms replace elements that match the given value or for which the given predicate evaluates to true.

\cppversions{\texttt{replace, replace\_if}}{\CC98}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{forward\_range}}{\texttt{forward\_range}}{N/A}{\texttt{unary\_predicate}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/aPrWhxxsj}{\ExternalLink}}
\footnotesize Example of using \cpp{std::replace} and \cpp{std::replace_if}.
\tcblower
\cppfile{code_examples/algorithms/replace_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::reverse}}{\texttt{std::reverse}}}
\index{\cpp{std::reverse}}

The \cpp{std::reverse} algorithm will reverse the order of elements in the range by applying \cpp{std::swap} to pairs of elements.

\cppversions{\texttt{reverse}}{\CC98}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{bidirectional\_range}}{\texttt{bidirectional\_range}}{}{}

Note that using \cpp{std::reverse} is only a reasonable solution if the range must be mutated because bidirectional ranges already support reverse iteration.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/onsj6dvqK}{\ExternalLink}}
\footnotesize Example of using \cpp{std::reverse} and reverse iteration, provided by bidirectional ranges.
\tcblower
\cppfile{code_examples/algorithms/reverse_code.h}
\end{codebox}

C-style arrays and C-style strings can be adapted using \cpp{std::span} and \texttt{std::string\-\_view} to allow reverse iteration.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/YW8sEa4c3}{\ExternalLink}}
\footnotesize Example of using \cpp{std::span} and \cpp{std::string_view} to addapt C-style constructs for reverse iteration.
\tcblower
\cppfile{code_examples/extras/span_stringview_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::rotate}}{\texttt{std::rotate}}}
\index{\cpp{std::rotate}}

The \cpp{std::rotate} algorithm rearranges elements in the range from \texttt{[first, middle),} \texttt{[middle, last)} to \texttt{[middle, last),} \texttt{[first, middle)}.

\cppversions{\texttt{rotate}}{\CC11}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{(forward\_range, forward\_iterator)}}{\texttt{(forward\_range, forward\_iterator)}}{}{}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/dP7TMfjKv}{\ExternalLink}}
\footnotesize Example of using \cpp{std::rotate}.
\tcblower
\cppfile{code_examples/algorithms/rotate_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::shift_left}, \cpp{std::shift_right}}{\texttt{std::shift\_left}, \texttt{std::shift\_right}}}
\index{\cpp{std::shift_left}}
\index{\cpp{std::shift_right}}

The \cpp{std::shift_left} and \cpp{std::shift_right} algorithms move elements in the provided range by the specified amount of positions.
However, unlike std::rotate, the shift doesn't wrap around.

\cppversions{\texttt{shift\_left}}{\CC20}{\CC20}{\CC20}{\CC20}
\cppversions{\texttt{shift\_right}}{\CC20}{\CC20}{\CC20}{\CC20}
\constraints{\texttt{forward\_range}}{\texttt{forward\_range}}{}{}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/5Tjh3M5Kv}{\ExternalLink}}
\footnotesize Example of using \cpp{std::shift_left} and \cpp{std::shift_right} with a trivially copyable type.
\tcblower
\cppfile{code_examples/algorithms/shift_code.h}
\end{codebox}

One way to think about these algorithms is that they "make space" for the requested number of new elements.

\begin{codebox}[breakable]{\href{https://compiler-explorer.com/z/sbY3fxYrs}{\ExternalLink}}
\footnotesize Example of using \cpp{std::shift_right} to make space for four new elements. Note that \texttt{'d'} wasn't moved as there is no place to move it to, and in the context of "making space" will be overwritten anyway.
\tcblower
\cppfile{code_examples/algorithms/shift_move_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::shuffle}}{\texttt{std::shuffle}}}
\index{\cpp{std::shuffle}}

The \cpp{std::shuffle} algorithm is a successor of the now-defunct (deprecated in \CC14, removed in \CC17) \cpp{std::random_shuffle} algorithm and relies on new random facilities added in \CC11.

\cppversions{\texttt{shuffle}}{\CC11}{N/A}{N/A}{\CC20}
\constraints{\texttt{random\_access\_range}}{}{}{}

\begin{codebox}[breakable]{\href{https://compiler-explorer.com/z/PE3bM8Gof}{\ExternalLink}}
\footnotesize Example of using \cpp{std::shuffle} to shuffle a deck of cards.
\tcblower
\cppfile{code_examples/algorithms/shuffle_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::next_permutation}, \cpp{std::prev_permutation}}{\texttt{std::next\_permutation}, \texttt{std::prev\_permutation}}}
\index{\cpp{std::next_permutation}}
\index{\cpp{std::prev_permutation}}

The \cpp{std::next_permutation} and \cpp{std::prev_permutation} algorithms will rearrange the element so that they are in their next or previous (by lexicographical comparison) permutation. When there is no such ordering, both algorithms will wrap around, but will also return \cpp{false} to notify the caller.

\cppversions{\texttt{next\_permutation}}{\CC98}{\CC20}{N/A}{\CC20}
\cppversions{\texttt{prev\_permutation}}{\CC98}{\CC20}{N/A}{\CC20}
\constraints{\texttt{bidirectional\_range}}{}{\texttt{operator <}}{\texttt{strict\_weak\_ordering}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/shfGz3brv}{\ExternalLink}}
\footnotesize Example of using \cpp{std::next_permutation} to iterate over all permutations of three unique elements.
\tcblower
\cppfile{code_examples/algorithms/next_permutation_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::is_permutation}}{\texttt{std::is\_permutation}}}
\index{\cpp{std::is_permutation}}

The \cpp{std::is_permutation} algorithm is an excellent tool for checking whether two ranges have the same content but not necessarily the same order of elements.

\cppversions{\texttt{is\_permutation}}{\CC11}{\CC20}{\CC17}{\CC20}
\constraints{\texttt{(forward\_range, forward\_range)}}{\texttt{(forward\_range, forward\_range)}}{\texttt{operator==}}{\texttt{binary\_predicate}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/axqfP6aaT}{\ExternalLink}}
\footnotesize Example of using \cpp{std::is_permutation} to validate a simple sort implementation.
\tcblower
\cppfile{code_examples/algorithms/is_permutation_code.h}
\end{codebox}
